LeetCode 205、同构字符串

一、题目描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add" 输出：true

示例 2：

输入：s = "foo", t = "bar" 输出：false

示例 3：

输入：s = "paper", t = "title" 输出：true

提示：

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

二、题目解析

三、参考代码

class Solution {
    public boolean isIsomorphic(String s, String t) {
        // 设置一个哈希映射用来存储字符串s中的元素
        HashMap<Character, Character> map1 = new HashMap<>();
        
        // 设置一个哈希映射用来存储字符串t中的元素
        HashMap<Character, Character> map2 = new HashMap<>();

        // 由于t.length == s.length
        // 按顺序访问s和t中对应的元素
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            // 1. 如果元素charS已经存在于map1中
            // 并且对应的值与当前元素charT不相同，返回false
            if (map1.containsKey(charS) && map1.get(charS) != charT) {
                return false;
            }

            // 2. 如果元素charT已经存在于map2中
            // 并且对应的值与当前元素charS不相同，返回false
            if (map2.containsKey(charT) && map2.get(charT) != charS) {
                return false;
            }

            // 3. 如果元素charS不存在于map1中，将其放入哈希映射中
            if (!map1.containsKey(charS)) {
                map1.put(charS, charT);
            }

            // 4. 如果元素charT不存在于map2中，将其放入哈希映射中
            if (!map2.containsKey(charT)) {
                map2.put(charT, charS);
            }
        }

        // 返回true
        return true;
    }
}

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        // 创建哈希映射用于存储字符串s中的元素
        unordered_map<char, char> map1;
        
        // 创建哈希映射用于存储字符串t中的元素
        unordered_map<char, char> map2;

        // 由于t.length == s.length
        // 按顺序访问s和t中对应的元素
        for (int i = 0; i < s.length(); i++) {
            char charS = s[i];
            char charT = t[i];

            // 1. 如果元素charS已经存在于map1中
            // 并且对应的值与当前元素charT不相同，返回false
            if (map1.count(charS) && map1[charS] != charT) {
                return false;
            }

            // 2. 如果元素charT已经存在于map2中
            // 并且对应的值与当前元素charS不相同，返回false
            if (map2.count(charT) && map2[charT] != charS) {
                return false;
            }

            // 3. 如果元素charS不存在于map1中，将其放入哈希映射中
            if (!map1.count(charS)) {
                map1[charS] = charT;
            }

            // 4. 如果元素charT不存在于map2中，将其放入哈希映射中
            if (!map2.count(charT)) {
                map2[charT] = charS;
            }
        }

        // 返回true
        return true;
    }
};

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:

        # 设置一个哈希集合用来存储字符串 s 当中的元素
        dic1 = {}

        # 设置一个哈希集合用来存储字符串 t 当中的元素
        dic2 = {}

        # 由于 t.length == s.length
        # 按照顺序访问 s 和 t 中对应的元素
        for i in range(len(s)):

            # 1、访问的元素 s[i] 存在于 dic1 中
            # 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            # 返回 False
            if s[i] in dic1 and dic1[s[i]] != t[i]:
                return False

            # 2、访问的元素 t[i] 存在于 dic2 中
            # 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            # 返回 False
            if t[i] in dic2 and dic2[t[i]] != s[i]:
                return False

            # 3、访问的元素 s[i] 不存在于 dic1 中
            # 存放到哈希集合中
            if s[i] not in dic1:
                # dic1[s[i]] = t[i]
                dic1[s[i]] = t[i]

            # 3、访问的元素 t[i] 不存在于 dic2 中
            # 存放到哈希集合中
            if t[i] not in dic2:
                # dic2[t[i]] = s[i]
                dic2[t[i]] = s[i]
        # 返回 True
        return True